package leetcode.offer;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _61_旋转链表 {

    /**
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        // 一、找到 (k % length个结点，记为结点A)
        int n = 0;
        ListNode node = head;
        // 获取链表的长度
        while (node != null) {
            node = node.next;
            n++;
        }
        // 获取第k个结点的真实位置
        k = k % n;
        // 旋转0次，就是返回原链表
        if (k == 0) return head;
        // 找到第k个结点
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        assert prev != null;
        prev.next = null;
        // 找到以slow为头结点的尾结点
        ListNode tail = slow;
        while (tail != null && tail.next != null) {
            tail = tail.next;
        }
        // 二、将结点A后的链表和头结点连接
        assert tail != null;
        tail.next = head;
        return slow;
    }
}
